package cp;

import java.util.Stack;

/**
 *
 * 20 有效的括号
 * Created by 程程有小棉被啊 on 2020年12月17日.
 */
public class LeetCode_20 {

    /*

    给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
    有效字符串需满足：
        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。
        注意空字符串可被认为是有效字符串。
    实例：
        输入: "()"            输出: true
        输入: "()[]{}"        输出: true
        输入: "(]"            输出: false
        输入: "([)]"          输出: false
        输入: "{[]}"          输出: true
     思路：
        需要维护一个栈进行匹配括号，遇到前括号(,[,{将其放入栈中，遇到后括号),],}
        跟栈顶元素匹配，看是否为一组完整的括号，若不是则返回false
     */

    public static void main(String[] args) {
        String s = "([)]";
        String s2 = "{[]}";
        System.out.println(vaildate(s));
        System.out.println(vaildate2(s));
    }


    static boolean vaildate(String s){
        if (s.length() % 2 != 0){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }
            if (c == ')'){
                if (!stack.isEmpty() && '(' == stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
            }
            if (c == ']'){
                if (!stack.isEmpty() && '[' == stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
            }
            if (c == '}'){
                if (!stack.isEmpty() && '{' == stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    static boolean vaildate2(String s){
        final char small = '(';
        final char middle = '[';
        final char big = '{';
        final char endSmall = ')';
        final char endMiddle = ']';
        final char endBig = '}';

        if (s.length() % 2 == 0){
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == small || c == middle || c == big){
                    stack.push(c);
                    continue;
                }
                if (c == endSmall && stack.peek() == small){
                    stack.pop();
                }else if (c == endMiddle && stack.peek() == middle){
                    stack.pop();
                }else if (c == endBig && stack.peek() == big){
                    stack.pop();
                }else{
                    return false;
                }
            }
            return stack.isEmpty();
        }
        return false;
    }



}
